\begin{section}{Desarrollo}
\begin{subsection}{Sistema de ecuaciones asociado al spline}
\par \noindent
Para encontrar los coeficientes de cada uno de los polinomios cúbicos del spline es necesario manipular de forma conveniente las condiciones necesarias para encontrar un sistema de ecuaciones a resolver que permita encontrar los coeficientes buscados.

\paragraph{} \noindent
Usando la definición de spline,
\\
\par 
$S(x_j) = f(x_j)$ y $S(x_j) = a_j$ $\forall j,$ $j=0,\dots,n-1$ entonces $a_j = f(x_j)$ $\forall j,$ $j=0,\dots,n-1$
\\
\par 
$S_{j+1}(x_{j+1}) = S_j(x_{j+1})$ y $S_{j+1}(x_{j+1}) = a_{j+1}$ $\forall j,$ $j=0,\dots,n-2$ entonces \\
\hspace*{20pt} $S_j(x_{j+1}) = d_j{(x_{j+1}-x_j)}^3 + c_j{(x_{j+1}-x_j)}^2 + b_j{(x_{j+1}-x_j)} + a_j = a_{j+1}$ $\forall j,$ $j=0,\dots,n-2$
\\
\begin{center} Sean $a_n = f(x_n)$ y $h_i = x_{i+1} - x_i$ $\forall i = 0, \dots, n-1$, entonces \end{center}
\begin{equation}
a_j = f(x_j) \quad \forall j, \; j=0,\dots,n
\end{equation}
\begin{equation}
a_{j+1} = d_j{h}^3 + c_j{h}^2 + b_j{h} + a_j \quad \forall j, \; j=0,\dots,n-1
\end{equation}
\\
%~ \par 
$S'_{j+1}(x_{j+1}) = S'_j(x_{j+1})$ y $S'_{j+1}(x_{j+1}) = b_{j+1}$ $\forall j,$ $j=0,\dots,n-2$ entonces \\
\hspace*{60pt} $S'_j(x_{j+1}) = 3.d_j{h}^2 + c_j{h} + b_j = b_{j+1}$ $\forall j,$ $j=0,\dots,n-2$
\begin{center} Sea $b_n = S'(x_n)$, entonces \end{center}
\begin{equation}
b_{j+1} = 3.d_j{h}^2 + 2.c_j{h} + b_j \quad \forall j, \; j=0,\dots,n-1
\end{equation}
\\
\par 
$S''_{j+1}(x_{j+1}) = S''_j(x_{j+1})$ y $S''_{j+1}(x_{j+1}) = 2.c_{j+1}$ $\forall j,$ $j=0,\dots,n-2$ entonces \\
\hspace*{80pt} $\displaystyle \frac{S''_j(x_{j+1})}{2} = 3.d_j{h} + c_j = c_{j+1}$ $\forall j,$ $j=0,\dots,n-2$
\begin{center} Sea $c_n = \displaystyle \frac{S''(x_n)}{2}$, entonces \end{center}
\begin{equation}
c_{j+1} = 3.d_j{h} + c_j \quad \forall j, \; j=0,\dots,n-1
\end{equation}
\\
\par
De esta forma todas las incógnitas pueden expresarse en función de los $c_i$
\begin{equation}
d_{j} = \displaystyle \frac{c_{j+1} - c_j}{3 h_j} \quad \forall j, \; j=0,\dots,n-1
\end{equation}
Usando que $b_{j+1} = b_j + h_j(c_j + c_{j+1})$ y $a_{j+1} = a_j +b_jh_j + \displaystyle \frac{h^2}{3} (2c_j + c_{j+1})$ $\forall j,$ $j=0,\dots,n-1$ entonces
\begin{equation}
\displaystyle b_j = \frac{1}{h_{j}} (a_{j+1}-a_{j}) - \frac{h_j}{3} (2c_{j}+c_{j+1}) \quad \forall j, \; j=0,\dots,n-1
\end{equation}
y 
\begin{equation}
\displaystyle h_{j-1}c_{j-1} + 2(h_{j-1} + h_j)c_j + h_jc_{j+1} = \frac{3}{h_{j}} (a_{j+1}-a_{j}) - \frac{3}{h_{j+1}} (a_{j}-a_{j-1}) \quad \forall j, \; j=0,\dots,n-1
\end{equation}

\par \noindent
El sistema $Ax = b$ es el sistema de ecuaciones asociado al spline.

\paragraph{}
\begin{center}
$\displaystyle A = \begin{pmatrix} 
   1 & 0 & 0 & \ldots & \ldots & \ldots & 0 
\\ h_0 & 2(h_0+h_1) & h_1 & 0 & \ldots & \ldots & 0 
\\ 0 & h_1 & 2(h_1 + h_2) & h_2 & 0 & \ldots & 0
\\ 0 &  \ddots & \ddots & \ddots & 0 & \ldots & 0
\\ \vdots & \ldots & h_{i+1} & 2(h_{i+1} + h_i) & h_i & \ldots & \vdots
\\ 0 & \ldots & 0 & \ddots & \ddots & \ddots & 0
\\ 0 & \ldots & 0 & h_{n-2} & 2(h_{n-3} + h_{n-2}) & h_{n-2} & 0
\\ 0 & \ldots & \ldots & 0 & h_{n-2} & 2(h_{n-2} + h_{n-1}) & h_{n-1}
\\ 0 & \ldots & \ldots & \ldots & 0 & 0 & 1 \end{pmatrix} $
\end{center}

\paragraph{}
\begin{center}
$\displaystyle x = \begin{pmatrix} c_0 \\ c_1 \\ \vdots \\ c_{n-1} \\ c_n \end{pmatrix} $
$\displaystyle B = \begin{pmatrix} 0
\\ \displaystyle \frac{3}{h_1} (a_2-a_1) - \frac{3}{h_0} (a_1-a_0)
\\ \vdots
\\ \displaystyle \frac{3}{h_{n-1}} (a_n-a_{n-1}) - \frac{3}{h_{n-2}} (a_{n-1}-a_{n-2})
\\ 0 \end{pmatrix} $
\end{center}

\paragraph{}
Como $c_0 = 0$ y $c_n = 0$ el sistema es equivalente a
\begin{center}
$\displaystyle A = \begin{pmatrix} 
  2(h_0+h_1) & h_1 & 0 & \ldots & 0 
\\ h_1 & 2(h_1 + h_2) & h_2 & \ldots & 0
\\ \ddots & \ddots & \ddots & \ldots & 0
\\ \vdots & h_{i+1} & 2(h_{i+1} + h_i) & h_i & \vdots
\\ \ldots & \ddots & \ddots & \ddots & 0
\\ \ldots & 0 & h_{n-2} & 2(h_{n-3} + h_{n-2}) & h_{n-2}
\\ \ldots & \ldots & 0 & h_{n-2} & 2(h_{n-2} + h_{n-1}) \end{pmatrix} $
\end{center}

\paragraph{}
\begin{center}
$\displaystyle x = \begin{pmatrix} c_1 \\ \vdots \\ c_{n-1} \end{pmatrix} $
$\displaystyle B = \begin{pmatrix} 
 \displaystyle \frac{3}{h_1} (a_2-a_1) - \frac{3}{h_0} (a_1-a_0)
\\ \vdots
\\ \displaystyle \frac{3}{h_{n-1}} (a_n-a_{n-1}) - \frac{3}{h_{n-2}} (a_{n-1}-a_{n-2}) \end{pmatrix} $
\end{center}

\paragraph{}
Siento $A$ una matr\'iz sim\'etrica y tridiagonal.

\end{subsection}

\begin{subsection}{Punto más próximo a la curva}

\par Para resolver el problema de c\'omo calcular el punto perteneciente a la curva m\'as cercano al que el usuario hace referencia, se necesita manipular la idea de \textit{distancia a la curva.} \\


\par Sean $S_x(t)$ y $S_y(t)$ los splines en $x$ y en $y$ respectivamente, que reciben a $t$ como parámetro, se denomina:
\paragraph{}

\textbf{Función distancia}
\begin{equation}
\displaystyle dist(t) = \sqrt{(x - S_x(t))^2 + (y - S_y(t))^2}
\end{equation}

\par Como se desea minimizar la distancia a la curva, se utilizan los puntos cr\'iticos que se hallen de la funci\'on que representa la distancia al cuadrada; la cual resulta m\'as f\'acil de manipular que la funci\'on distancia. Esto es v\'alido porque la funci\'on elevar al cuadrado es continua y creciente. Los puntos cr\'iticos pueden hallarse de manera conveniente encontrando los ceros de la derivada de la funci\'on. 
\paragraph{}

\textbf{Función distancia al cuadrado}
\begin{equation}
f(t) = (x - S_x(t))^2 + (y - S_y(t))^2
\end{equation}

\textbf{Derivada}
\begin{equation}
f'(t) = 2(x - S_x(t))(-S'_x(t)) + 2(y - S_y(t))(-S'_y(t))
\end{equation}

\par Como se buscan los ceros de la funci\'on derivada, se desean hallar los $t$s que cumplan que $f'(t) = 0$ por lo tanto es lo mismo encontrar los ceros de la funci\'on $f'(t)$ que de 
\begin{equation}
(S_x(t) - x)(S'_x(t)) + (S_y(t) - y)(S'_y(t))
\end{equation}

\par Para encontrar los ceros, se utilizaron diversos m\'etodos. Primero se dividi\'o el intervalo $[0, 1]$ de $t$ (ya que en el programa se normaliza la parametrizaci\'on para que $t$ quede siempre entre $0$ y $1$ inclusive), en $1000*n$ partes iguales y luego se aplic\'o bisecci\'on y regula\_falsi en cada subintervalo. Como los intervalos son \textsl{chicos} se pens\'o que es razonable suponer que s\'olo con evaluar la funci\'on en los bordes puede saberse si en ese intervalo hay o no un cero. La raz\'on es que si la funci\'on no cambia de signo y el intervalo es lo suficientemente chico, entonces es poco probable que haya un cero en ese intervalo. Por lo tanto en los m\'etodos de bisecci\'on y regula\_falsi (explicados a continuaci\'on) cuando aparece este caso (en el que la funci\'on tiene el mismo signo en los bordes) devuelve algunos de los dos bordes seg\'un cu\'al de los dos minimice la distancia al click.

\end{subsection}

\begin{subsection}{Bisecci\'on}

\par

Para calcular los ceros de la funci\'on derivada, se comienza utlizando el algoritmo de bisecci\'on. Para ello, hay que recordar:

\paragraph{}

\fboxrule = 1.0pt
\shadowsize = 1.0pt

 \textbf{Teorema de Bolzano:}

\paragraph{}

\shadowbox{
\begin{minipage}[l][0.05 \textheight][c]{1.0\textwidth}
\begin{center}
\textbf{Sea $f: [a,b]$ $\subset R^2$ una funcion continua en $[a,b]$ tq $f(a).f(b)<0$ . Entonces $\exists c $ $ \in (a,b)$  tq $f(c)=0 $}
\end{center}
\end{minipage}
}



 \par El Teorema de Bolzano afirma que si una función es continua en un intervalo cerrado y acotado y en los extremos del mismo ésta toma valores con signos opuestos, entonces existe al menos una raíz de la función en el interior del intervalo.
\paragraph{}

 \textbf{Teorema del Valor Intermedio:}


\paragraph{}

\shadowbox{
\begin{minipage}[l][0.05 \textheight][c]{1.0\textwidth}
\begin{center}
\textbf{Sea $f: [a,b]$ $\subset \Re \rightarrow \Re$  continua en $[a,b]$ tq $f(a)< f(b)$
 Entonces, para cualquier $k$ tq $f(a)< k < f(b) $  $\exists$  $ x_0$   $\in (a,b)$  tq $f(x_0)=k $}
\end{center}
\end{minipage}
}


 \par Básicamente el Teorema del Valor Intermedio dice que toda función contínua en
un intervalo cerrado, una vez que alcanza ciertos valores en los extremos del intervalo,
entonces debe alcanzar todos los valores intermedios.

\par Finalmente:

\paragraph{}

 \textbf{M\'etodo de Bisecci\'on:}

\par Se basa en estos teoremas y se emplea para aproximar ceros de funciones. Por ejémplo, se quiere encontrar los ceros de una función $f(x)$ continua. Dados dos puntos $a$ y $b$ tal que:

\paragraph{}
\begin{equation}
f(a).f(b) < 0  
\end{equation}

\par Se sabe por el \textit{Teorema de Bolzano} que $f(x)$ debe tener, al menos, una raíz en el intervalo [a, b]. A continuaci\'on, el método de bisección divide el intervalo en dos, usando un tercer punto:

\paragraph{}
\begin{equation}
c = \frac{a+b}{2} 
\end{equation}

 \par En este momento existen dos posibilidades:
\paragraph{}
\begin{equation}
f(a).f(c)<0
\end{equation}

\begin{equation}
 f(c).f(b)<0
\end{equation}

\par El método de bisección se aplica al subintervalo donde el cambio de signo ocurre. Este proceso puede aplicarse tantas veces como sea necesario para alcanzar la precisión que se requiera.

\par En este trabajo para realizar bisección se realizó una función llamada \textbf{multi\_biseccion}. Esta toma, entre otros parámetros, un vector de intervalos. Estos son subintervalos del intervalo de valores del dibujo. Lo que realiza es aplicar bisección a cada subintervalo, y finalmente, quedarse con el de valor más cercano al click realizado por el usuario.

\end{subsection}

\begin{subsection}{M\'etodo de Newton}
\par  Para calcular el punto más cercano a la curva, otro de los métodos utilizados es el método de Newton. El cual, para ser utilizado, requiere de un punto inicial cercano a la raíz deseada. Luego, en cada iteración se obtiene un punto que tiende al cero deseado. Para esto realiza la siguiente cuenta:

\begin{equation}
x_{n+1} = x_n - \frac{f(x)}{f'(x)}
\end{equation}

En el caso de este trabajo la función utilizada es la derivada de la función distancia. Por ello la derivada utilizada en este método es la segunda derivada de la función distancia. A continuación se presenta dicha función:

\begin{equation}
f''(t) = 2((S'_x(t))^2 + (x - S_x(t)) * S''_x(t)) + 2((S'_y(t))^2 + (y - S_y(t)) * S''_y(t))
\end{equation}

\par Este método dado que no toma un intervalo como parámetro, sino que toma un valor cercano al cero deseado, para este trabajo se decidió utilizarlo como método para mejorar el cero encontrado tanto con bisección como con Regula Falsi, el cual se explica a continuación.

\end{subsection}


\begin{subsection}{M\'etodo Regula Falsi}

 \par El último método para calcular la distancia, es el Método Regula Falsi. Este toma un intervalo inicial $[a_0,b_0]$ tq $f(a_0)$ y $f(b_0)$ tienen signos opuestos, de forma similar a bisección. En cada paso se va achicando el intervalo que contiene la raíz, hasta llegar a la solución. En cada iteración se calcula el elemento $c_k$ de la siguiente manera:
 
	\begin{equation}
		c_k = \frac{f(b_k)a_k - f(a_k)b_k}{f(b_k)-f(a_K)}
	\end{equation} 
 
\par Al igual que bisección, en este trabajo, para utilizar este método se creo una función llamada \textbf{multi\_regula\_falsi} que realiza lo mismo que multi\_biseccion pero llamando al método regula\_falsi.


\end{subsection}

\begin{subsection}{Modificaci\'on del Spline}
\begin{enumerate}
	\item Se busca el punto m\'as cercano al click perteneciente a la curva, usando los m\'etodos descriptos.
	\item Se agrega el punto de control correspondiente, teniendo en cuenta que su orden relativo depende del valor de t encontrado. Se agregan los pares $(t, \bar{x}^*)$ y, $(t, \bar{y}^*)$ a los puntos de control parametrizados en x, e y.	
	\item Se recalcula el spline usando el m\'etodo de interpolaci\'on con splines.
\end{enumerate}
\end{subsection}


\begin{subsection}{Verificaci\'on del spline}

\paragraph{} 
Una vez calculado el spline, es necesario verificar que el resultado obtenido es el correcto. Para lograr esto se utiliza la definici\'on de Spline natural, mostrada en la introducci\'on te\'orica. Recordar que:


\begin{enumerate}
		\item $S(x)$ es un polinomio de grado $3$ en $[x_j, x_{j+1}]$ $\forall j,$ $j=0,\dots,n-1$	 
		\item $S(x_j) = f(x_j)$ $\forall j,$ $j=0,\dots,n$		
		\item $S_{j+1}(x_{j+1}) = S_j(x_{j+1})$ $\forall j,$ $j=0,\dots,n-2$ (continuidad).
		\item $S'_{j+1}(x_{j+1}) = S'_j(x_{j+1})$ $\forall j,$ $j=0,\dots,n-2$ (derivadas iguales de ambos lados)
		\item $S''_{j+1}(x_{j+1}) = S''_j(x_{j+1})$ $\forall j,$ $j=0,\dots,n-2$ (concavidades iguales de ambos lados)
		\item $S''(x_{0}) = 0$ y $S''(x_{n}) = 0$, (spline natural.)
		  

	\end{enumerate}
	

Se realiz\'o una funci\'on que verifica la correctitud de los splines, verificando cada una de estas condiciones. En principio, el programa no devolv\'ia la respuesta correcta (no pasaba la verificaci\'on), por lo tanto, fue necesario comprobar las splines resultantes \textit{a mano}.
\end{subsection}

\begin{subsection}{Visualizaci\'on de los splines}
\par Se consider\'o conveniente tener una visualizaci\'on de las curvas de los splines. Para esto, se realiz\'o una funci\'on graficadora, que muestrea los splines en x y en y en una cantidad \textsl{grande} de puntos. Primero se muestrea uniformemente el intervalo $[0, 1]$ de $t$ en $1000*n$ partes y luego se evalua en cada punto. Usando estos puntos, se realiza un gr\'afico utilizando el programa \textbf{octave}.

\end{subsection}
\end{section}
